' Written by Craig'n'Dave
Module Module1
    ' Linked list using an array
    Public Class LinkedList
        Private start As Integer = -1
        Private next_free As Integer = 0
        Private max As Integer = 10
        Private llist(max, 2) As String

        Sub New()
            ' Initialise the free items list
            For index = 0 To max - 1
                llist(index, 1) = Convert.ToString(index + 1)
            Next
            llist(max - 1, 1) = "-1"
        End Sub

        Function add(item As String)
            Dim current_node As Integer = start
            Dim previous_node As Integer = 0
            Dim new_node As Integer
            ' Check memory overflow
            If next_free <> -1 Then
                new_node = next_free
                llist(new_node, 0) = item
                next_free = Convert.ToInt32(llist(next_free, 1))
                ' List is empty
                If start = -1 Then
                    llist(new_node, 1) = "-1"
                    start = new_node
                Else
                    ' Item becomes the new start item
                    If item < llist(current_node, 0) Then
                        start = new_node
                        llist(new_node, 1) = Convert.ToString(current_node)
                    Else
                        ' Find correct position in the list
                        Do While current_node <> -1 AndAlso llist(current_node, 0) < item
                            previous_node = current_node
                            current_node = Convert.ToInt32(llist(current_node, 1))
                        Loop
                        llist(new_node, 1) = llist(previous_node, 1)
                        llist(previous_node, 1) = Convert.ToString(new_node)
                    End If
                End If
                Return True
            Else
                Return False
            End If
        End Function

        Sub delete(item)
            Dim current_node As Integer = start
            Dim previous_node As Integer = 0
            ' Check the list is not empty
            If current_node <> -1 Then
                ' Item is the start node
                If item = llist(current_node, 0) Then
                    start = Convert.ToInt32(llist(current_node, 1))
                Else
                    ' Find the item in the list
                    Do While current_node <> -1 And item <> llist(current_node, 0)
                        previous_node = current_node
                        current_node = Convert.ToInt32(llist(current_node, 1))
                    Loop
                    llist(previous_node, 1) = llist(current_node, 1)
                End If
                ' Return deleted node to the free list
                llist(current_node, 1) = Convert.ToString(next_free)
                next_free = current_node
            End If
        End Sub

        Function output()
            Dim items = New List(Of String)
            Dim current_node As Integer = start
            If start <> -1 Then
                ' Visit each node
                Do While current_node <> -1
                    items.Add(llist(current_node, 0))
                    current_node = Convert.ToInt32(llist(current_node, 1))
                Loop
            End If
            Return items
        End Function

    End Class

    'Main program starts here
    Sub Main()
        Dim items() As String = { "Florida", "Georgia", "Delaware", "Alabama", "California", "Wyoming" }
        Dim linked_list As New LinkedList
        ' Adding items to the linked list
        For index = 0 To items.Length - 1
            linked_list.add(items(index))
        Next
        ' Deleting items from a linked list
        linked_list.delete("Florida")
        ' Output the linked list
        Dim contents = New List(Of String)
        contents = linked_list.output()
        Console.WriteLine(String.Join(", ", contents))
    End Sub

End Module
